package com.jzoffer;

import java.util.ArrayList;
import java.util.Iterator;

// 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
public class TheLeastKNum {
    public static void main(String[] args) {
        int [] input = {4,5,9,6,2,7,3,1};
        ArrayList<Integer> integers = GetLeastNumbers_Solution(input, 4);
        Iterator<Integer> iterator = integers.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            System.out.println(next);
        }

    }

    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k){
        ArrayList<Integer> res = new ArrayList<>();
        if(input == null || input.length < 1 || k < 1 || k > input.length){
            return res;
        }
        int len = input.length;
        // 使用冒泡排序算法 得到前k小个数，并添加到集合之中
        for(int i = len - 1,y = 0;i > len - 1 - k;i--){
            for (int j = len - 1 ; j > y;j--){
                if(input[j - 1] > input[j]){
                    swap(input,j - 1,j);
                }
            }
            res.add(input[y]);
            y++;
        }
        return res;
    }

    private static void swap(int [] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
